public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] stones = new int[]{2,7,4,1,8,1};
        System.out.println(test.lastStoneWeightII(stones));
    }

    public int lastStoneWeightII(int[] stones) {
        /**
         * 最后一块石头的重量
         * 状态表示：
         *  dp[i][j]表示在前i个元素中进行挑选，使其体积不超过j，此时的最大体积
         * 状态转移方程：
         *
         * 初始化：
         *  无需初始化，使用虚拟位置法
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return 差值
         * */
        // 1 预处理
        int n = stones.length;
        int total = 0;
        for(int x: stones) {
            total += x;
        }
        int t = total / 2;
        // 2 创建dp表
        int[][] dp = new int[n+1][t+1];
        // 3 初始化

        // 4 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= t; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= stones[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j-stones[i-1]] + stones[i-1], dp[i][j]);
                }
            }
        }
        // 5 返回值
        return total - dp[n][t] * 2;
    }
}
